package com.remove.lsh.utils;

public final class TestString {

    public  static  String x1 =
            "在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度，怎样快速地从海量的高维数据" +
                    "集合中找到与某个数据最相似（距离最近）的一个数据或多个数据成为了一个难点和问题。如" +
                    "果是低维的小数据集，我们通过线性查找（LinearSearch）就可以容易解决，但如果是对一个海量的高维数" +
                    "据集采用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们需要采" +
                    "用一些类似索引的技术来加快查找过" +
                    "程，通常这类技术称为最近邻查找（Nearest  Neighbor,AN），例如K-d tree；或近似最近邻查找" +
                    "（Approximate Nearest  Neighbor, ANN），例如K-d tree with BBF, Randomized Kd-trees, Hierarchical " +
                    "K-means Tree。而LSH是ANN中的一类方法。我们知道，通过建立Hash Table的方式我们能够得到O(1)的查找时间性能，其" +
                    "中关键在于选取一个hash function，将原始数据映射到相对应的桶内（bucket, hash bin），例如对数据求模：h = x mod " +
                    "w，w通常为一个素数。在对数据集进行hash的过程中，会发生不同的数据被映射到了同一个桶中（即发生了冲突collision），这" +
                    "一般通过再次哈希将数据映射到其他空桶内来解决。这是普通Hash方法或者叫传统Hash方法，其与L" +
                    "SH有些不同之处。LSH的基本思想是：将原始数据空间中的两个相邻数据" +
                    "点通过相同的映射或投影变换（projection）后，这两个数据点在新" +
                    "的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同" +
                    "一个桶的概率很小。也就是说，如果我们对原始数据进行一些hash" +
                    "映射后，我们希望原先相邻的两个数据能够被hash到相同的桶内，具有" +
                    "相同的桶号。对原始数据集合中所有的数据都进行hash映射后，我们就得" +
                    "到了一个hash table，这些原始数据集被分散到了hash table的桶内，" +
                    "每个桶会落入一些原始数据，属于同一个桶内的数据就有很大可能是相邻的，" +
                    "当然也存在不相邻的数据被hash到了同一个桶内。因此，如果我们能够找到这样一" +
                    "些hash functions，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入" +
                    "相同的桶内的话，那么我们在该数据集合中进行近邻查找就变得容易了，我们只需要" +
                    "将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行线性" +
                    "匹配即可查找到与查询数据相邻的数据。换句话说，我们通过hash function映射变换操作" +
                    "，将原始数据集合分成了多个子集合，而每个子集合中的数据间是相邻的且该子集合" +
                    "中的元素个" +
                    "数较小，因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集" +
                    "合内查找相邻元素的问题，显然计算量下降了很多。LSH的应用场景很多，凡是需要" +
                    "进行大量数据之间的相似度（或距离）计算的地方都可以使用LSH来加快查找匹配速度，" +
                    "下面列举一些应用：（1）查找网络上的重复网页互联网上由于各式各样的原因（例如转载、抄袭等" +
                    "）会存在很多重复的网页，因此为了提高搜索引擎的检索质量或避免重复建立索引，需要查找出重复" +
                    "的网页，以便进行一些处理。其大致的过程如下：将互联网的文档用一个集合或词袋向量来表征，然后" +
                    "通过一些hash运算来判断两篇文档之间的相似度，常用的有minhash+LSH、simhash。（2）查找相似新" +
                    "闻网页或文章与查找重复网页类似，可以通过hash的方法来判断两篇新闻网页或文章是否相似，只不过" +
                    "在表达新闻网页或文章时利用了它们的特点来建立表征该文档的集合。（3）图像检索在图像检索领域" +
                    "，每张图片可以由一个或多个特征向量来表达，为了检索出与查询图片相似的图片集合，我们可以对图" +
                    "片数据库中的所有特征向量建立LSH索引，然后通过查找LSH索引来加快检索速度。目前图像检索技术在" +
                    "最近几年得到了较大的发展，有兴趣的读者可以查看基于内容的图像检索引擎的相关介绍。（4）音乐检索" +
                    "对于一段音乐或音频信息，我们提取其音频指纹（Audio Fingerprint）来表征该音频片段，采用音频指" +
                    "纹的好处在于其能够保持对音频发生的一些改变的鲁棒性，例如压缩，不同的歌手录制的同一条歌曲等。" +

                    "为了快速检索到与查询音频或歌曲相似的歌曲，我们可以对数据库中的所有歌曲的音频指纹建立LSH" +
                    "索引，然后通过该索引来加快检索速度。（5）指纹匹配一个手指指纹通常由一些细节来表征，通" +
                    "过对比较两个手指指纹的细节的相似度就可以确定两个指纹是否相" +
                    "同或相似。类似于图片和音乐检索，我们可以对这些细节特征建立LSH索引，加快指纹的匹配速" +
                    "度。   三、LSH family我们在第一节介绍了LSH的原理和LSH hash function需要满足的条件，回顾一" +
                    "下：满足以下两个条件的hash functions称为(d1,d2,p1,p2)-sensitive： 1）如果d(x,y) ≤ d1， 则h(x) = h(y)的概率至少" +
                    "为p1；2）如果d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；d(x,y)是x和y之间的一个" +
                    "距离度量（distance measure），需要说明的是，并不是所有的距离度量都能够找到满足locality-se" +
                    "nsitive的hash functions。 下面我们介绍一些满足不同距离度量方式下的locality-sensitive的hash functions：1. Jaccard distanceJaccard distance：" +
                    " (1 - Jaccard similarity)，而Jaccard similarity = (A intersection B) / (A union B)，Jac" +
                    "card similarity通常用来判断两个集合的相似性。 Jaccard distance对应的LSH hash function为：m" +
                    "inhash，其是(d1,d2,1-d1,1-d2)-sensitive的。 2. Hamming distanceHamming distance： 两个具有相同长度的向量中对应位置处值不同的次数。 Hamming distance对应的LSH hash " +
                    "function为：H(V) = 向量V的第i位上的值，其是(d1,d2,1-d1/d,1-d2/d)-sensitive的。 3. Cosine" +
                    " distance Cosine distance：cos(theta) = A·B / |A||B| ，常用来判断两个向量之间的夹角，" +
                    "夹角越小，表示它们越相似。 Cosine distance对应的LSH hash function为：H(V) = sign(V·R)，R是" +
                    "一个随机向量。V·R可以看做是将V向R上进行投影操作。其是(d1,d2,(180-d1)180,(180-d2)/180)-sensitiv" +
                    "e的。 理解：利用随机的超平面（random hyperplane）将原始数据空间进行划分，每一个数据被投" +
                    "影后会落入超平面的某一侧，经过多个随机的超平面划分后，原始空间被划分为了很多cell，而位于每个c" +
                    "ell内的数据被认为具有很大可能是相邻的（即原始数据之间的cosine distance很小）。  4. normal Euclidea" +
                    "n distanceEuclidean distance是衡量D维空间中两个点之间的距离的一种距离度量方式。 Euclidean distanc" +
                    "e对应的LSH hash function为：H(V) = |V·R + b| / a，R是一个随机向量，a是桶宽，b是一个在[0," +
                    "a]之间均匀分布的随机变量。V·R可以看做是将V向R上进行投影操作。其是(a/2,2a,1/2,1/3)-sensitive的。";
}
